package pri.zjy.linkedList;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangjy
 * @description 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * @date 2025/2/20 10:07
 */
public class LRUCache_146_2 {

    public static void main(String[] args) {

        LRUCache_146_2 lruCache = new LRUCache_146_2(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }

    /**
     * 个人解法——错误！！！put逻辑错误
     */

    // 双向链表
    class DoubleLinkedListNode {

        private Integer key;

        private Integer value;

        DoubleLinkedListNode prev;

        DoubleLinkedListNode next;

        public DoubleLinkedListNode() {

        }

        public DoubleLinkedListNode(Integer key, Integer value, DoubleLinkedListNode prev, DoubleLinkedListNode next) {
            this.key = key;
            this.value = value;
            this.prev = prev;
            this.next = next;
        }

    }

    private Map<Integer, DoubleLinkedListNode> map;

    private DoubleLinkedListNode head;

    private DoubleLinkedListNode tail;

    private int count = 0;

    private int capacity;

    public LRUCache_146_2(int capacity) {
        this.map = new HashMap<>(capacity);
        this.head = new DoubleLinkedListNode();
        this.tail = new DoubleLinkedListNode();
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
    }

    public int get(int key) {
        // key不存在，返回-1
        if (!map.containsKey(key)) {
            return -1;
        }

        // key存在，把对应节点移动到链表头部（移动已有node，所以count和map不改变）
        // 1.移除节点node（不一定在尾部，可能在中间）
//        removeLastNode();
        DoubleLinkedListNode node = map.get(key);
        removeNode(node);

        // 2.node插入头部
        addNodeToHead(node);

        // head指向node
//        DoubleLinkedListNode tmp = head.next;
//        // head和node互相连接
//        head.next = node;
//        node.prev = head;
//        // 原首个节点和node互相连接
//        node.next = tmp;
//        tmp.prev = node;

        // 返回节点值
        return node.value;
    }

    public void put(int key, int value) {
        // put逻辑错误（因为相同key，可对应不同value）
        // 不应该根据容量是否满来决定，直接插入新node，还是先移除尾部节点再插入
        // 应该是先判断key是否存在，若存在，则更新对应value；反之，再根据容量决定插入逻辑（参照LRUCache_146的put方法）

        // 还有空间，则直接存
        DoubleLinkedListNode node = new DoubleLinkedListNode(key, value, null, null);
        if (count < capacity) {
            // 插入首个节点，还需要处理tail
            if (count == 0) {
                tail.prev = node;
            }
            // 插入非首个节点，只处理head
            insertNode(key, node);
            return;
        }
        // 空间耗尽，需要淘汰（tail指针指向的就是最近最少使用数据）
        // 1.先移除尾部节点
        removeLastNode();

        // 2.新节点node插入头部
        insertNode(key, node);
    }

    public void insertNode(int key, DoubleLinkedListNode node) {
        // 插入节点
        DoubleLinkedListNode tmp = head.next;
        // 1.head和node互相连接
        head.next = node;
        node.prev = head;
        // 2.原首个节点和node互相连接
        node.next = tmp;
        tmp.prev = node;
        map.put(key, node);

        count++;
    }

    public void removeLastNode() {
        // 1.从缓存中移除
        map.remove(tail.prev.key);
        count--;
        // 2.移除尾部节点
//        tail.prev.prev.next = tail;
//        tail.prev = tail.prev.prev;
        removeNode(tail.prev);
    }

    private void removeNode(DoubleLinkedListNode node) {
        // node的前驱节点和后继节点指向批次，从而移除node
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addNodeToHead(DoubleLinkedListNode node) {
        // 1.旧next和新node指向彼此
        head.next.prev = node;
        node.next = head.next;
        // 2.head和新node指向彼此
        head.next = node;
        node.prev = head;
    }

}
